package leetcode;

import java.util.Arrays;
import java.util.List;

public class CountSmallerNumbersAfterSelf2 {

	public static void main(String[] args) {
		CountSmallerNumbersAfterSelf2 object = new CountSmallerNumbersAfterSelf2();
		int[] nums = {3, 2, 2, 6, 1};
		System.out.println(object.countSmaller(nums));
	}
	
	
	//二叉搜索树
//	 For example, [3, 2, 2, 6, 1]
//	  1(0, 1)
//       \
//       6(3, 1)
//       /
//     2(0, 2)
//        \
//         3(0, 1)
	private class Node {
        Node left, right;
        //sum recording the total of number on it's left bottom side
        //但是并不代表比当前结点小的数，因为比当前小的还含有在该结点左上方的
        //times表示出现的次数
        int val, sum, times = 1;
        public Node(int v, int s) {
            val = v;
            sum = s;
        }
    }
	
	public List<Integer> countSmaller(int[] nums) {
        Integer[] ans = new Integer[nums.length];
        Node root = null;
        //该BST是自下向上的
        for (int i = nums.length - 1; i >= 0; i--) {
            root = insert(nums[i], root, ans, i, 0);
        }
        return Arrays.asList(ans);
    }
	
	private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
        if (node == null) {
            node = new Node(num, 0);
            ans[i] = preSum;
            System.out.println("node: " + node.val + "  preSum: " + preSum + "  " + ans[i]);
        } else if (node.val == num) {
        	//node所代表的值出现次数加1
            node.times++;
            ans[i] = preSum + node.sum;
            System.out.println("node: " + node.val + "  " + ans[i]);
        } else if (node.val > num) {
        	node.sum++;
            node.left = insert(num, node.left, ans, i, preSum);
            System.out.println("node: " + node.val + "  " + node.sum + "  left smaller " + ans[i]);
        } else {
        	System.out.println("node: " + node.val + "preSum: " + preSum + " times: " + node.times 
        			+ " " + node.sum);
        	//如果num大于node的值，注意这是自下向上的，num位于node之前
        	
        	//计算出该结点的preSum： preSum + node.times + node.sum
        	//preSum是父节点中小于该结点的
        	//node.times是该结点的次数
        	//node.sum是左下方，也即小于该结点的左子树的结点数
            node.right = insert(num, node.right, ans, i, preSum + node.times + node.sum);
        }
        return node;
    }
}
